#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "hashmap.h"

#define DEFAULT_SIZE 16

struct node
{
	const char *key;
	void *value;
	struct node *next;
};

struct hashmap
{
	int size;
	int cap;
	struct node **array;
};

struct hashmap *hashmap_new()
{
	struct hashmap *map = malloc(sizeof(*map));
	map->size = 0;
	map->cap = DEFAULT_SIZE;
	map->array = calloc(sizeof(struct node*), map->cap);

	return map;
}

void hashmap_release(struct hashmap *map)
{
	assert(map);

	int i;
	for (i = 0; i < map->cap; ++i)
	{
		struct node *tmp, *n = map->array[i];
		while(n != NULL)
		{
			tmp = n;
			n = n->next;
			free(tmp);
		}
	}

	free(map->array);
	free(map);
}

int hash_int(int key, int length)
{
	return key & (length - 1);
}

static int hash_str(const char *key, int length)
{
    const char *sno = key;
    unsigned int index = 0;

    while (*sno)
    {
        index = *sno + 4*index;
        sno++;
    }

    return index & (length - 1);
}

struct node *node_malloc(const char *key, void *value)
{
	struct node *n = malloc(sizeof(*n));
	n->key = key;
	n->value = value;
	n->next = NULL;

	return n;
}

static void hashmap_reset(struct hashmap *map)
{
	int i, sz = map->cap * 2;

	struct node **newarray = calloc(sizeof(struct node*), sz);

	for (i = 0; i < map->cap; ++i)
	{
		struct node *tmp, *head = map->array[i];
		while (head)
		{
			tmp = head;
			head = head->next;

			int idx = hash_str(tmp->key, sz);
			struct node *old = newarray[idx];

			if (old != NULL)
			{
				tmp->next = old;
			}
			else
			{
				tmp->next = NULL;
			}
			newarray[idx] = tmp;
		}
	}

	free(map->array);
	map->array = newarray;
	map->cap = sz;
}

void hashmap_push(struct hashmap *map, const char *key, void *value)
{
	if (map->size > map->cap * 3 / 4)
	{
		hashmap_reset(map);
	}

	int idx = hash_str(key, map->cap);

	struct node *new = node_malloc(key, value);
	struct node *old = map->array[idx];

	new->next = old;
	
	map->array[idx] = new;
	map->size ++;
}

void *hashmap_get(struct hashmap *map, const char *key)
{
	int idx = hash_str(key, map->cap);
	struct node *n = map->array[idx];
	if (n == NULL)
	{
		return NULL;
	}

	if (strcmp(n->key, key) == 0)
	{
		return n->value;
	}

	n = n->next;

	while(n)
	{
		if (strcmp(n->key, key) == 0)
		{
			return n->value;
		}
		n = n->next;
	}

	return NULL;
}

int hashmap_size(struct hashmap *map)
{
	return map->size;
}

void hashmap_dump(struct hashmap *map, callback cb)
{
	int i;
	for (i = 0; i < map->cap; i++)
	{
		struct node *n = map->array[i];

		if (n)
		{
			cb(n->value);
		}
	}
}

